<!DOCTYPE html>
<html lang="en">
	<head>
		<meta charset="UTF-8" />
		<meta http-equiv="X-UA-Compatible" content="IE=edge" />
		<meta name="viewport" content="width=device-width, initial-scale=1.0" />
		<title>红黑树</title>
	</head>
	<body>
		<!--
		红黑树的基本概念 ：
    1. 节点必须是红或黑色  
		2. 根节点是黑色  
    3. 每一个叶子节点都是黑色的空节点 NIL 
		4. 每个红色节点的两个子节点都是黑色 （红色节点不可能连续出现）
    5. 从任意节点到每一个子节点的所有路径都包含相同数目的黑色节点
		 -->
		<!-- 
      变色：
        1. 初始创建节点为红色
      左旋转：
        1. 逆时针旋转 左平移
      右旋转：
        1. 顺时针旋转 右平移
      -->

		<!-- 插入  新节点为红色-->
		<!-- 
        1. 第一种情况：P为根节点，且根为空节点
          + 颜色变黑
          + 加两个NIL 
        2. 第二种情况:  P为黑色
          + 直接插入
          + 加两个NIL 
        3. 第三种情况: P为红色 U为红色
          + P红 U红 G黑 
          + P黑 U黑 G红     
          + 递归处理
        4. 第四种情况 P红 U黑 G黑 N为左子节点
          + P黑 G红 U不变 
          + 右旋转 
        5. 第五种情况 P红 U黑 G黑 N为右子节点
          + 以P为根左旋转
          + 将P作为新节点插入（转成情况四）           
      -->
	</body>
</html>
